package sort

/**
 * 排序算法	平均时间复杂度
 * 插入排序     O(n2)
 * 基本思想
 * 在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，
 * 使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
 */

fun main(arr: Array<String>) {
    insertionSort(getItems())
}

/**
 * 插入排序
 */
fun insertionSort(arr: ArrayList<Int>) {
    var temp: Int
    //遍历集合
    for (i in 0 until arr.size - 1) {
        //类似于扑克牌插入，越遍历越多，对集合进行最小值比较
        for (j in i + 1 downTo 1) {
            if (arr[j] < arr[j - 1]) {
                temp = arr[j]
                arr[j] = arr[j - 1]
                arr[j - 1] = temp
            } else {
                break
            }
        }
    }

    print(arr)
}